package com.fr.lintcode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

/**
*作者：furong
*日期：2017年3月23日
*时间：下午4:26:12
*/
public class Q178 {
    /**
     * @param n an integer
     * @param edges a list of undirected edges
     * @return true if it's a valid tree, or false
     */
    public boolean validTree(int n, int[][] edges) {
        if (n <= 1) {
            return true;
        }
        Map<Integer, Node> map = new HashMap<>();
        // 无孤点、无环
        for (int[] a : edges) {
            Node a0 = map.get(a[0]);
            if (a0 == null) {
                a0 = new Node();
                a0.value = a[0];
                a0.set.add(a[1]);
                map.put(a[0], a0);
            } else {
                a0.set.add(a[1]);
            }
            Node a1 = map.get(a[1]);
            if (a1 == null) {
                a1 = new Node();
                a1.value = a[1];
                a1.set.add(a[0]);
                map.put(a[1], a1);
            } else {
                a1.set.add(a[0]);
            }
        }
        if (map.size() != n) {
            return false;
        }
        boolean change = true;
        while (change) {
            change = false;
            for (Node node : map.values()) {
                if (node.set.size() == 1) {
                    for (int i : node.set) {
                        Node old = map.get(i);
                        old.set.remove(node.value);
                    }
                    node.set.clear();
                    change = true;
                }
            }
        }
        for (Node node : map.values()) {
            if (node.set.size() > 1) {
                return false;
            }
        }
        return true;
    }

    class Node {
        int value;
        Set<Integer> set = new HashSet<>();
    }

    @Test
    public void testA() {
        int n = 5;
        int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 }, { 1, 3 }, { 1, 4 } };
        System.out.println(validTree(n, edges));
    }
}
